﻿// 0731train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <string>
#include <limits.h>

using namespace std;


/*
 给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，
 请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
 */

void solve01(vector<int>&numbers, int target)
{
    vector<int>oh_vec = numbers;
    vector<int>result_vec(2);

    int left = 0;
    int right = oh_vec.size() - 1;

    while (left<right)
    {
        int sum = oh_vec[left] + oh_vec[right];
        
        if (sum<target)
        {
            left++;
        }
        else if (sum > target)
        {
            right--;
        }
        else
        {
            result_vec[0] = left+1;
            result_vec[1] = right+1;
            break;
        }
	    //while------
    }

    for (auto&item:result_vec)
    {
        cout << item << ' ';
    }

    //solve01
    //------
}



/*
 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，
 原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1]
输出：[0,1,2]
 */

void Swap(vector<int>& nums, int left, int right)
{
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;

	//swap------
}

void solve02(vector<int>&nums)
{
    int left = 0;
    int right = nums.size() - 1;
    int index = 0;

    while (index<=right)
    {
        int curr = nums[index];

        if (curr==0)
        {
            Swap(nums, left, index);
            left++;
            index++;
        }
        else if (curr==1)
        {
            index++;
        }
        else if (curr==2)
        {
            Swap(nums, index, right);
            right--;
        }

        //while------
    }
      

    for (auto&item:nums)
    {
        cout << item << ' ';
    }

	//solve02
    //------
}


/*
 给你一个字符串 s，最多 可以从中删除一个字符。
请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。 
示例 1：
输入：s = "aba"
输出：true
示例 2：
输入：s = "abca"
输出：true
解释：你可以删除字符 'c' 。
示例 3：
输入：s = "abc"
输出：false 
 */

bool IsPalindrome(string oh_str)
{
    int left = 0;
    int right = oh_str.size()-1;

    
    while (left<right)
    {
	    if (oh_str[left]!=oh_str[right])
	    {
            return false;
	    }
        left++;
        right--;
    }
    return true;
    //------
}

bool IsPalindrome131(string oh_str, int low, int high)
{
    int left = low;
    int right = high;

    while (left<right)
    {
        if (oh_str[left]!=oh_str[right])
        {
            return false;
        }
        left++;
        right--;

    }
    return true;
    //------
}

//bool solve03(string s)
//{
//    if (IsPalindrome(s)) return true;
//
//    string oh_str = s;
//    int str_size = oh_str.size();
//
//    string str_first = oh_str.substr(1, str_size - 1);
//    string str_last = oh_str.substr(0, str_size - 1);
//    if (IsPalindrome(str_first)||IsPalindrome(str_last))
//    {
//        return true;
//    }
//
//    bool result = false;
//    //abca //
//    for (int i=1; i< str_size-1; i++)
//    {
//        string new_str1 = oh_str.substr(0, i);
//        string new_str2 = oh_str.substr(i + 1, str_size - i - 1);
//        string new_str = new_str1 + new_str2;
//        if (IsPalindrome(new_str))
//        {
//            result = true;
//            break;
//        }
//        //cout << verify_str << endl;
//        //for-----
//    }
//
//    return result;
//
//    //solve03
//}

bool solve131(string s)
{
    string oh_str = s;
    int str_size = s.size();
    int low = 0;
    int high = str_size - 1;

    while (low<high)
    {
        if (oh_str[low]==oh_str[high])
        {
            low += 1;
            high -= 1;

        }
        else
        {
            return IsPalindrome131(oh_str, low + 1, high) || IsPalindrome131(oh_str, low, high - 1);
        }
    }
    return true;
    //solve131
}


int main()
{
	{
        //cout << IsPalindrome131("abca", 1,2);
        cout << solve131("aba");
        return 0;
	}

	{
        //nums = [2,0,2,1,1,0]

        vector<int>nums = { 2,0,2,1,1,0 };
        solve02(nums);
        return 0;
	}

    //numbers = [2,7,11,15], target = 9
    vector<int>oh_vec = { 2,7,11,15 };
    int target = 9;
    solve01(oh_vec, target);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
